package com.fw.leetcode.binarysearch;

import com.fw.leetcode.LeetCode;

import java.util.Arrays;
import java.util.Comparator;

/**
 * 436. Find Right Interval
 *
 * You are given an array of intervals, where intervals[i] = [start i, end i] and each start i is unique.
 *
 * The right interval for an interval i is an interval j such that start j >= end i and start j is minimized.
 * Note that i may equal j.
 *
 * Return an array of right interval indices for each interval i.
 * If no right interval exists for interval i, then put -1 at index i.
 *
 * Example 1:
 *  Input: intervals = [[1,2]]
 *  Output: [-1]
 *  Explanation: There is only one interval in the collection, so it outputs -1.
 *
 * Example 2:
 *  Input: intervals = [[3,4],[2,3],[1,2]]
 *  Output: [-1,0,1]
 *  Explanation: There is no right interval for [3,4].
 *  The right interval for [2,3] is [3,4] since start0 = 3 is the smallest start that is >= end1 = 3.
 *  The right interval for [1,2] is [2,3] since start1 = 2 is the smallest start that is >= end2 = 2.
 *
 * Example 3:
 *  Input: intervals = [[1,4],[2,3],[3,4]]
 *  Output: [-1,2,-1]
 *  Explanation: There is no right interval for [1,4] and [3,4].
 *  The right interval for [2,3] is [3,4] since start2 = 3 is the smallest start that is >= end1 = 3.
 *
 * Constraints:
 *  1 <= intervals.length <= 2 * 10^4
 *  intervals[i].length == 2
 *  -10^6 <= start i <= end i <= 10^6
 *  The start point of each interval is unique.
 */
public class Num_0436 implements LeetCode {

    private interface Solution {
        int[] findRightInterval(int[][] intervals);

        default void assertExpected(int[][] nums, int[] expected) {
            if (!Arrays.equals(findRightInterval(nums), expected)) {
                findRightInterval(nums);
            }
        }
    }

    private static class IndexSortBinarySearchSolution implements Solution {
        public int[] findRightInterval(int[][] intervals) { // 排序 + 二分：时O(nlog n)+O(nlog n) 空O(n)
            // 额外存储 [start i -> i] 的索引，并以 start i 排序
            int[][] startIndex = new int[intervals.length][2];
            for (int i = 0; i < intervals.length; i++) {
                startIndex[i] = new int[]{intervals[i][0], i};
            }
            // 排序 => 会导致原数组元素和索引号丢失，需要额外存储
            Arrays.sort(startIndex, Comparator.comparingInt(elm -> elm[0]));
            // 遍历
            int[] result = new int[intervals.length];
            for (int i = 0; i < intervals.length; i++) {
                if (i == intervals.length - 1) { // 最后一个元素最大，肯定没有右区间
                    result[result.length - 1] = -1;
                }
                // 二分
                int left = 0;
                int right = startIndex.length - 1;
                int mid;
                int maybe = -1;
                while (left <= right) {
                    mid = (left + right) / 2;
                    if (startIndex[mid][0] >= intervals[i][1]) { // 满足 end i <= start j，向前找更小的
                        maybe = startIndex[mid][1]; // 记录索引
                        right = mid - 1;
                    } else { // 不满足 end i <= start j，向后找更大的
                        left = mid + 1;
                    }
                }
                result[i] = maybe;
            }
            return result;
        }
    }

    public static void main(String[] args) {
        Solution solution = new IndexSortBinarySearchSolution();
        solution.assertExpected(new int[][]{{1,2}}, new int[]{-1});
        solution.assertExpected(new int[][]{{3,4},{2,3},{1,2}}, new int[]{-1,0,1});
        solution.assertExpected(new int[][]{{1,4},{2,3},{3,4}}, new int[]{-1,2,-1});
    }
}
